# -*- coding: utf-8 -*-

"""剑指 Offer II 101. 分割等和子集
给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100"""


class Solution:
    """一开始看到这题，竟然没有头绪，后面再读题，这不就是经典的0-1背包问题吗？
    此时也能更深刻理解动态规划了，从头到尾遍历数组，没遇到一个数，都可以做取与不取的决策，这是回溯的流程
    当遍历到一个数做决策后，都有一堆可能的和，这堆可能的和是固定的，就可以用动态规划来解决。
    同时可以维护一个哈希表便可，每遍历一个数，里面的求和结果集就会更新，最后看这个集合里面是否有需要的总和一半"""
    def canPartition(self, nums) -> bool:
        if len(nums) == 1:
            return False
        
        if sum(nums) % 2:
            return False

        totals = set()
        totals.add(0)
        for n in nums:
            dp = set()
            for t in totals:
                dp.add(t)
                dp.add(t+n)
            totals = dp

        return sum(nums)//2 in totals


if __name__ == '__main__':
    so = Solution()
    print(so.canPartition([1,5,11,5]))
    print(so.canPartition([1,2,3,5]))
